from leetcode_test import *


class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        ans = []
        if root is None:
            return []

        def helper(root, sum, res):
            if root is None:
                return
            if root.val == sum and not root.left and not root.right:
                ans.append(res + [root.val])

            helper(root.left, sum - root.val, res + [root.val])
            helper(root.right, sum - root.val, res + [root.val])

        helper(root, sum, [])
        return ans


def test():
    t = TreeNode.create([5, 4, 8, 11, None, 13, 4, 2, 2, None, None, None, 1])
    assert Solution().pathSum(t, 22) == [[5, 4, 11, 2], [5, 8, 4, 5]]


def test1():
    t = TreeNode.create([1, 2])
    assert Solution().pathSum(t, 1) == []
    assert Solution().pathSum(t, 3) == [[1, 2]]


def test3():
    t = TreeNode.create([])
    assert Solution().pathSum(t, 0) == []


    